class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray_rec(nums, 0, nums.size()-1);
    }

    int maxSubArray_rec(vector<int>& nums, int l, int r){
        if(l == r)
            return nums[l];

        int mid = (l + r) / 2;
        int left = maxSubArray_rec(nums, l, mid);
        int right = maxSubArray_rec(nums, mid+1, r);

        int left_num = nums[mid];
        int tmp = 0;
        for(int i=mid; i>=l; i--){
            tmp += nums[i];
            left_num = max(left_num, tmp);
        }

        int right_num = nums[mid+1];
        tmp = 0;
        for(int i=mid+1; i<=r; i++){
            tmp += nums[i];
            right_num = max(right_num, tmp);
        }

        return max(left_num + right_num, max(left, right));
    }
};